package com.agile.leetcode.hot.middle;

/**
 * 236. 二叉树的最近公共祖先
 * 给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。
 * <p>
 * 百度百科中最近公共祖先的定义为：“对于有根树 T 的两个节点 p、q，最近公共祖先表示为一个节点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”
 * <p>
 * <p>
 * <p>
 * 示例 1：
 * <p>
 * <p>
 * root:为层次遍历的结果，倒推树结构的时候应该用层次遍历来倒推
 * 输入：root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1
 * 输出：3
 * 解释：节点 5 和节点 1 的最近公共祖先是节点 3 。
 * 示例 2：
 * <p>
 * <p>
 * 输入：root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 4
 * 输出：5
 * 解释：节点 5 和节点 4 的最近公共祖先是节点 5 。因为根据定义最近公共祖先节点可以为节点本身
 *
 * @Author:ChenZhangKun
 * @Date: 2021/4/29 10:12
 */
public class LowestCommonAncestor {
    public static void main(String[] args) {
        TreeNode treeNode7 = new TreeNode(7, null, null);
        TreeNode treeNode4 = new TreeNode(4, null, null);
        TreeNode treeNode2 = new TreeNode(2, treeNode7, treeNode4);
        TreeNode treeNode6 = new TreeNode(6, null, null);
        TreeNode treeNode5 = new TreeNode(5, treeNode6, treeNode2);
        TreeNode treeNode0 = new TreeNode(0, null, null);
        TreeNode treeNode8 = new TreeNode(8, null, null);
        TreeNode treeNode1 = new TreeNode(1, treeNode0, treeNode8);
        TreeNode treeNode3 = new TreeNode(3, treeNode5, treeNode1);
        LowestCommonAncestor lowestCommonAncestor = new LowestCommonAncestor();
        System.out.println(lowestCommonAncestor.lowestCommonAncestor(treeNode3, treeNode5, treeNode1));
    }

    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if (root == null) {
            return root;
        }
        // 是否是与p或q相等
        if (root == p) {
            return p;
        }
        if (root == q) {
            return q;
        }
        // 递归
        // 先从左子树进行比对，如果匹配到就返回
        TreeNode left = lowestCommonAncestor(root.left, p, q);
        // 然后从右子树进行匹配
        TreeNode right = lowestCommonAncestor(root.right, p, q);
        if (left != null && right != null) {
            // 两个都匹配到，说明主树才是祖先
            return root;
        }
        // 匹配到的左边子树
        if (left != null) {
            return left;
        }
        // 匹配到右边子树
        if (right != null) {
            return right;
        }
        // 没有匹配到返回null
        return null;
    }
}

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    public TreeNode(int val) {
        this.val = val;
    }

    public TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }

    @Override
    public String toString() {
        return "TreeNode{" +
                "val=" + val +
                ", left=" + left +
                ", right=" + right +
                '}';
    }
}
